package leetcode;


import java.util.ArrayList;
import java.util.List;

public class PermutationSequence {

	public static void main(String[] args) {
		PermutationSequence object = new PermutationSequence();
		System.out.println(object.getPermutation(4, 8));
	}
	
    public String getPermutation(int n, int k) {
        if(n == 1 && k > 1){
        	return null;
        }
        if(n == 1 && k <= 1){
        	return String.valueOf(1);
        }
        //1 ~ 9 的阶乘
        int[] factorial = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        List<Integer> list = new ArrayList<>();
        list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);
        list.add(6);list.add(7);list.add(8);list.add(9);
        StringBuilder builder = new StringBuilder();
        n--;	//只需要求k / (n - 1)!的商即可
        while(n >= 1){
        	//如果商的范围在(0,1],那么就是选择1，(1, 2]就选择2
        	//所以要处理去大于等于的最大值
        	int index = (int)Math.ceil((double)k / factorial[n - 1]) - 1;
        	System.out.println("index: " + index);
        	builder.append(list.get(index));
        	k -= index * factorial[n - 1];
        	n--;
        	list.remove(index);
        }
        //最后添加最后一个值，此时list中只有一个值了
        builder.append(list.get(0));
        return builder.toString();
    }
}
